package leetcode.editor.vscdev.hot100;

import java.util.*;

public class lc3 {

    public static void main(String[] args) {
        String s = "pwwkew";
        System.out.println(new Solution().lengthOfLongestSubstring(s));
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int max = 0;
        int l = 0;
        Set<Character> set = new HashSet<>();// set集合用来查询重复元素
        char[] arr = s.toCharArray();

        for (int r = 0; r < arr.length; r++) {
            while (set.contains(arr[r])) {
                // 说明有重复的了, 依次移除窗口的元素直到无重复
                set.remove(arr[l]);
                l++;
            }
            set.add(arr[r]);
            // 选取最大值
            max = Math.max(max, r - l + 1);
        }
        return max;
    }

    public int func2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int res = 0;
        int l = 0;
        Map<Character, Integer> map = new HashMap<>();
        char[] arr = s.toCharArray();
        for (int r = 0; r < arr.length; r++) {
            // 此处map优化循环
            if (map.containsKey(arr[r])) {
                // 关键：确保左指针不会回退到之前的位置
                l = Math.max(l, map.get(arr[r]) + 1);
            }
            map.put(arr[r], r);
            res = Math.max(res, r - l + 1);
        }
        return res;
    }

    private int func3(String s) {
        char[] arr = s.toCharArray();
        int res = 0;
        // 该寻址数组索引为字符ASCII值, 值为该字符出现上一次位置 + 1
        int[] hash = new int[128];
        int l = 0;
        for (int r = 0; r < arr.length; r++) {
            // 左右指针元素相同, l跳到重复元素下一位
            l = Math.max(hash[arr[r]], l);
            // 更新res
            res = Math.max(res, r - l + 1);
            // 更新寻址数组当前数的出现位置 + 1
            hash[arr[r]] = r + 1;
        }
        return res;
    }
}
